# -*- coding: cp936 -*-

#include <stdio.h>



#define  STONE     3 //定义常量 石头(白色棋子)

#define  LEAF      7 //         树叶(黑色棋子)

#define  WHITE     0 //         白方用0表示

#define  BLACK     1 //         黑方用1表示

#define  NOPIECE   0 //         无棋子用0


int board[4][4] = { 
   3, 3, 3, 3,       
  3, 0, 0, 3,     
  7, 0, 0, 7,      
 7, 7, 7, 7       
 };
 
int board[64] = {
  0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 7, 7, 7, 7, 0, 0,
  0, 0, 7, 0, 0, 7, 0, 0,
  0, 0, 3, 0, 0, 3, 0, 0,
  0, 0, 3, 3, 3, 3, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0
};

#用来标记棋子是否在棋盘上的数组

static const int inBoard[64] = {
  0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 1, 1, 1, 1, 0, 0,
  0, 0, 1, 1, 1, 1, 0, 0,
  0, 0, 1, 1, 1, 1, 0, 0,
  0, 0, 1, 1, 1, 1, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0
};

#由棋盘数组下标获得棋子X坐标

int getXFromLocation(int location){
  return (location & 7) - 2;
} 

#由棋盘数组下标获得棋子Y坐标

int getYFromLocation(int location){
  return (location >> 3) - 2;
} 

#由棋子X坐标，Y坐标获得棋盘数组下标

int getLocationFromXY(int x, int y){
  return (x + 2) + (y + 2 << 3);
}


int currentPlayer = WHITE; #初始化为白方走棋，BLACK表示黑方走棋 


void changePlayer(){
  currentPlayer = 1 - currentPlayer; #改变走棋方，不是0 就是1 

}


#在棋盘上放一枚棋子的函数

void addPiece(int location){ #根据位置和当前走棋方添加棋子

  int piece;
  
  piece = currentPlayer * 4 + 3; #由当前走棋方计算当前走棋方棋子

  
  if(inBoard[location]){
    board[location] = piece;
  }
}

#在棋盘上拿走一枚棋子的函数

void delPiece(int location){ #根据位置删除棋子 

  if(inBoard[location]){
    board[location] = NOPIECE; #NOPIECE == 0表示无棋子 

  }
}



#根据走法生成走法起点位置(起点位置的棋盘数组下标)

int generateMoveFrom(int move){
  return move & 255;
}

#根据走法生成走法目的位置(目的位置的棋盘数组下标)

int generateMoveTo(int move){
  return move >> 8;
}

#由起点位置和目的位置合成走法

int composeMove(int locationFrom, int locationTo){
  return locationFrom + locationTo * 256;
}


#define MAX_GEN_MOVES 32 #定义一个常量来表示走法的最大生成数 


static int theMoves[MAX_GEN_MOVES]; #定义一个走法数组用来保存生成的所有走法，一个局面最多走法数不会超过MAX_GEN_MOVES种 


static const char movesTable[4] = {-8, 8, -1, 1}; #这个数组用来表示棋子的走子方向


#走法生成函数，产生一个局面的所有走法 

int generateAllMoves(int *moves){ #传递一个走法列表数组指针，返回生成的所有走法 

  int i, from, to, genCount;
  int myPiece, pieceFrom, pieceTo;
  
  #走法计数器清零

  genCount = 0;
  #获取当前走棋方标记

  myPiece = currentPlayer * 4 + 3; #根据当前走棋方，确定当前走棋方棋子 

  
  #遍历棋盘找到当前走棋方棋子

  for(from = 0; from < 64; from++){
    #取得当前位置的棋子

    pieceFrom = board[from];
    
    #1.如果找到的不是本方棋子，继续找

    if(pieceFrom != myPiece){ 
      continue;
    }
    
    #2.如果找到本方棋子，探测四个方向是否可走

    for(i = 0; i < 4; i++){
      to = from + movesTable[i]; #目标位置

      if(inBoard[to]){#如果还在棋盘内

        pieceTo = board[to]; #获取此位置棋子

        if(pieceTo == NOPIECE){#如果此位置无棋子，此走法可行 

          moves[genCount] = composeMove(from, to); #保存走法 

          genCount++; #计数

        } 
      } 
    }#end for(i)

    
  }#end for(from)

  return genCount; #返回生成的走法数

}


#吃子检查序列数组

static int eatSequence[2][2][4] = {
  {{7, 3, 3, 0},{0, 7, 3, 3}},
  {{3, 7, 7, 0},{0, 3, 7, 7}}
};

#检查吃子的函数，无返回吃子位置部分

int checkEat(int to){
  int i, j, k, step, eat, check; #检查吃子专用

  int pieceSequence[4]; #pieceSequence用来保存棋子序列(检查吃子时用)

  
  # 检查吃子，从上往下、从下往上、从左往右、从右往左，沿四个方向检查吃子情况

  # 比如：从左往右检查，只需检查是否呈“●○○_”或“_●○○”序列(假如白方为当前方)

  
  for(i = 0; i < 4; i++){
    
    #1. 取得焦点位置(焦点就是当前检查点)

    check = to; #check变量这时作为焦点位置

    
    #2. 取得步长

    step = movesTable[i];
    
    #3. 把焦点位置往反方向移动到棋盘边上

    while(inBoard[check]){
      check -= step; #往反方向移动焦点

    }
    
    #4. 往正方向取得棋子序列，保存在数组pieceSequence中

    for(j = 0; j < 4; j++){
      form += step; 
      if(inBoard[check]){
        pieceSequence[j] = board[check];
      }
    }
    
    #5. 把焦点位置再次往反方向移动到棋盘边上，以便由焦点位置根据吃子序列数组取得吃子位置

    while(inBoard[check]){
      check -= step; //往反方向移动焦点
    }
    
    #6. 检查棋子序列是否与两个吃子序列匹配，若匹配则吃子

    for(k = 0; k < 2; k++){
      #6.1 初始化为有子可吃

      eat = 1;
      #6.2 检查序列是否完全匹配

      for(j = 0; j < 4; j++){
        if(pieceSequence[j] != eatSequence[currentPlayer][k][j]){
          eat = 0;
        }
      }
      #6.3 检查到序列完全匹配则，按位置吃子

      if(eat == 1){
        delPiece(check + step * (k + 1)); 
      }
    }
  }
}

int makeOneMove(int move, int *eatTable){ #传递一个用来保存吃子位置的数组

  int i, genCount, isLegalMove, from, to;
  int step, focus, myPiece, oppPiece, eatCount; #吃子专用

  
  isLegalMove = 1; #初始化走法为不合法

  genCount = generateAllMoves(theMoves); #生成所有走法

#在所有走法中查找当前走法是否存在

  for(i = 0; i < genCount; i++){
#如果找到一个走法等于当前走法 

    if(theMoves[i] == move){
      isLegalMove = 0; #所有走法中有此走法，说明走法合法

      break; 
    }
  }
  
  #1.首先判断走法是否合法

  if(isLegalMove == 1){
    return 0; 
  }
  
  #2.分解走法，取得起点位置和目的位置

  from = generateMoveFrom(move);
  to = generateMoveTo(move);
  
  #3.走一步棋

  delPiece(from);
  addPiece(to);
  
 #4.检查吃子

  eatCount = 0; /#一步有可能同时吃掉两子

  myPiece = currentPlayer * 4 + 3;       #由当前走棋方计算当前走棋方棋子

  oppPiece = (1 - currentPlayer) * 4 + 3; #由当前走棋方计算对方棋子

  
  #检查吃子，从上往下、从下往上、从左往右、从右往左，沿四个方向检查吃子情况

  for(i = 0; i < 4; i++){
    
    step = movesTable[i]; 
    
    
    focus = to + step; 
    if(inBoard[focus] && board[focus] == myPiece){
      focus += step; 
      if(inBoard[focus] && board[focus] == oppPiece){
        focus += step; 
        if(inBoard[focus] && board[focus] == NOPIECE){
          focus -= step; 
          delPiece(focus); 
          eatTable[eatCount] = focus; 
          eatCount++; #计数

        }
      }
    }
    
   #检查是否为第二种吃子情况“○○●_” 所走棋子为序列中的第二个白子

    focus = to - step; #把焦点移到棋子后方位置

    if(inBoard[focus] && board[focus] == myPiece){
      focus = to + step; #把焦点移到棋子前方第一个位置

      if(inBoard[focus] && board[focus] == oppPiece){
        focus += step; #把焦点移到棋子前方第二个位置

        if(inBoard[focus] && board[focus] == NOPIECE){
          focus -= step; #把焦点移到吃子位置

          delPiece(focus); #/吃子

          eatTable[eatCount] = focus; #记录吃子的位置

          eatCount++; #计数

        }
      }
    }
   
   #检查是否为第三种吃子情况“●○○_” 所走棋子为序列中的第二个白子

    focus = to - step; 
    if(inBoard[focus] && board[focus] == oppPiece){
      focus = to + step; 
      if(inBoard[focus] && board[focus] == myPiece){
        focus += step; 
        if(inBoard[focus] && board[focus] == NOPIECE){
          focus = to - step; 
          delPiece(focus); 
          eatTable[eatCount] = focus;
          eatCount++; 
        }
      }
    }
   
    #检查是否为第四种吃子情况“_○○●” 所走棋子为序列中的第二个白子

    focus = to - step; 
    if(inBoard[focus] && board[focus] == NOPIECE){
      focus = to + step;
      if(inBoard[focus] && board[focus] == myPiece){
        focus += step; 
        if(inBoard[focus] && board[focus] == oppPiece){
          focus = focus;
          delPiece(focus); 
          eatTable[eatCount] = focus; 
          eatCount++; 
        }
      }
    }
   
  }
  
 #5.交换走棋方

  changePlayer();
  
  return 1 + eatCount; #返回吃子的个数加1，我们调用此函数时，只需要用返回值减1就得到吃子个数

}


#判断是否分出胜负的函数 

int isCurrentPlayerDie(){
  
#如果生成零个走法，则已被困死，将返回1

  if(generateAllMoves(theMoves)){
    return 0;
  }
  return 1;
}


#局面评估函数 

int evaluatePosition(){
  int i, whiteValue, blackValue, value;
  
#初始化双方的总价值

  whiteValue = blackValue = 0;
  
#遍历棋盘，找到棋子

  for(i = 0; i < 64; i++){
    if(board[i] == STONE){
      whiteValue += 3;
    }
    if(board[i] == LEAF){
      blackValue += 3;
    }
  }
#计算局面价值

  value = whiteValue - blackValue;
  
  return value;
}


#define SEARCH_DEPTH 7 //设置搜索深度

#define INFINITY_VALUE 100 //设置局面价值无穷大为100，因为局面价值最大为36，

                         #3100不可能达到，所以就相当于无穷大。 



int bestMove; 

#搜索深度

int theDepth; 

#撤销一步棋的函数 

void undoOneMove(int move, int eatCount, int *eatTable){
  int i, from, to;

  from = generateMoveFrom(move);
  to = generateMoveTo(move);
  
 #/还原被吃的子

  for(i = 0; i < eatCount; i++){
    addPiece(eatTable[i]);   }
  
  changePlayer(); 
  delPiece(to);   
  addPiece(from); 
}


int MinMaxSearch(int depth){
                              int i, genCount, value, bestValue;
  int allMoves[MAX_GEN_MOVES];
  int eatCount, eatTable[2]; 
  

  if(depth == 0){
    return evaluatePosition();
  }

  #初始化最佳值

  if(currentPlayer){
    bestValue = INFINITY_VALUE; #正无穷

  }else{
    bestValue = -INFINITY_VALUE; #负无穷

  }

  genCount = generateAllMoves(allMoves);
  
  for(i = 0; i < genCount; i++){
    eatCount = makeOneMove(allMoves[i], eatTable);#走棋

    if(eatCount){ #

      theDepth++;
      value = MinMaxSearch(depth - 1); #递归

      undoOneMove(allMoves[i], eatCount - 1, eatTable); #还原

      theDepth--;
      if(currentPlayer){#如果当前走棋方是黑方，找一个评分最小的局面(对黑方最有利) 

        if(value < bestValue){
          bestValue = value;
          if(depth == SEARCH_DEPTH){ #如果是根节点 保存最佳走法 

            bestMove = allMoves[i];
          }
        }
      }else{#如果当前走棋方是白方，找一个评分最大的局面(对白方最有利) 

        if(value > bestValue){
          bestValue = value;
          if(depth == SEARCH_DEPTH){ #如果是根节点 保存最佳走法 

            bestMove = allMoves[i];
          }
        } 
      }
    }
  }
  
#如果是杀棋，就根据距杀棋的步数给出评价

  if(currentPlayer){ #如果是黑方

    if(bestValue == INFINITY_VALUE){
      return INFINITY_VALUE - theDepth;
    }
  }else{ #是白方

    if(bestValue == -INFINITY_VALUE){
      return theDepth - INFINITY_VALUE;
    }
  }
  
  return bestValue; #返回找到的最佳局面评分

}


#让电脑走棋 

int computerThink(){
  int eatCount, eatTable[2];
  theDepth = 0;#距根结点的距离

  MinMaxSearch(SEARCH_DEPTH);
  eatCount = makeOneMove(bestMove, eatTable);
  return eatCount - 1; #3返回吃子个数

}


#3定义个变量用来设置电脑(引擎)是白方或者是黑方

int engine = BLACK;

#//写个翻转棋盘的函数

int flipLocation(int location){
  location = 63 - location;
  return location;
}


void showBoard(){
  int i, j, piece;
  int location;
  
  printf("\n");
  printf("                    y ********\n");
  for(i = 0; i < 4; i++){
    printf("                    %d ", i);
    for(j = 0; j < 4; j++){
      location = getLocationFromXY(j, i);
      
      if(engine == WHITE){ 
        location = flipLocation(location);
      }
      piece = board[location];
      if(piece == STONE){
        printf("●"); 
      }else if(piece == LEAF){
        printf("○"); 
      }else if(piece == NOPIECE){
        printf("╋");
      }else{
        printf(" ");
      }
    }
    printf("\n");
  }
  printf("                      ********\n");
  printf("                      0 1  2 3 x\n\n");
}

int main(){
  int move, from, to, fromX, fromY, toX, toY, eatTable[2];
  char command;
  

  int i, genCount, value, eatCount;
  
  genCount = generateAllMoves(theMoves); 
  
  printf("开局时，白方有%d种走法，分别是：\n", genCount);
  for(i = 0; i < genCount;i++){
      printf("from %d to %d \n", generateMoveFrom(theMoves[i]), generateMoveTo(theMoves[i]));
  }
  
  printf("开局时，局面的价值是：%d\n", evaluatePosition());
  
  eatCount = makeOneMove(theMoves[0], eatTable);
  
  printf("走棋后吃了%d颗子\n", eatCount - 1);
  
  undoOneMove(theMoves[0], eatCount - 1, eatTable);
  
  value = MinMaxSearch(SEARCH_DEPTH);
  
  printf("开局搜索局面，找到的最佳局面评分：%d\n", value);
  
  printf("开局搜索局面，找到的最佳走法是：from %d to %d \n", generateMoveFrom(bestMove), generateMoveTo(bestMove));

  
  
  
  showBoard(); 
  
  while(1){
    printf("\n输入Q退出，输入D下棋：");
    command = getch();
    if(command == 'q' || command == 'Q'){
      return 0;
    }
    if(command == 'd' || command == 'D'){ 
    
      printf("\n输入S选择石头(白棋)，输入L选择树叶(黑棋)：");
      command = getch();
      if(command == 's' || command == 'S'){ 
        engine = BLACK; 
        printf("\n您选择了石头(白棋)！\n");
      }else if(command == 'l' || command == 'L'){ 
        engine = WHITE; //设置引擎为白棋
        printf("\n您选择了树叶(黑棋)！\n");
      }else{
        continue;
      }
      while(1){
        if(isCurrentPlayerDie() && currentPlayer != engine){
          printf("\n不好意思，你已战败！再来一局请重新打开程序！\n");
          printf("\n输入q退出：");
          command = getch();
          if(command == 'q' || command == 'Q'){
            return 0;
          }
        }else if(isCurrentPlayerDie() && currentPlayer == engine){
          printf("\n恭喜你，电脑被你打败！再来一局请重新打开程序！\n");
          printf("\n输入q退出：");
          command = getch();
          if(command == 'q' || command == 'Q'){
            return 1;
          }
        }else{
          if(engine == WHITE){ 
            showBoard();
            if(1){ 
              printf("\n电脑正在思考...\n");
              computerThink();
              move = bestMove;
              from = generateMoveFrom(move); 
              to = generateMoveTo(move);
              from = flipLocation(from); 
              to = flipLocation(to);
              fromX = getXFromLocation(from); 
              fromY = getYFromLocation(from);
              toX = getXFromLocation(to);
              toY = getYFromLocation(to); 
              printf("\n电脑所走的棋是：from (%d,%d) to (%d,%d)\n", fromX, fromY, toX, toY);
              showBoard();
            }
            if(isCurrentPlayerDie()){ 
              continue;
            }
            if(1){ 
              printf("\n轮到您下棋，请输入坐标 x,y x,y ：");
              scanf("%d,%d %d,%d", &fromX, &fromY, &toX, &toY);
              printf("\n您走的棋是：from (%d,%d) to (%d,%d)\n", fromX, fromY, toX, toY);
              from = getLocationFromXY(fromX, fromY);
              to = getLocationFromXY(toX, toY);
              from = flipLocation(from); 
              to = flipLocation(to);
              move = composeMove(from, to);
              while(!makeOneMove(move, eatTable)){
                printf("\n输入坐标错误，请重新输入坐标：");
                scanf("%d,%d %d,%d", &fromX, &fromY, &toX, &toY);
                from = getLocationFromXY(fromX, fromY);
                to = getLocationFromXY(toX, toY);
                from = flipLocation(from); 
                to = flipLocation(to);
                move = composeMove(from, to); 
                getchar();
              }
            }
          }
          
          if(engine == BLACK){ 
            showBoard();
            if(1){
              printf("\n轮到您下棋，请输入坐标 x,y x,y ：");
              scanf("%d,%d %d,%d", &fromX, &fromY, &toX, &toY);
              printf("\n您走的棋是：from (%d,%d) to (%d,%d)\n", fromX, fromY, toX, toY);
              from = getLocationFromXY(fromX, fromY);
              to = getLocationFromXY(toX, toY);
              move = composeMove(from, to); 
              while(!makeOneMove(move, eatTable)){
                printf("\n输入坐标错误，请重新输入坐标：");
                scanf("%d,%d %d,%d", &fromX, &fromY, &toX, &toY);
                from = getLocationFromXY(fromX, fromY);
                to = getLocationFromXY(toX, toY);
                move = composeMove(from, to); 
                getchar();
              }
              showBoard();
            }
            if(isCurrentPlayerDie()){ 
              continue;
            }
            if(1){ 
              printf("\n电脑正在思考...\n");
              computerThink();
              move = bestMove;
              from = generateMoveFrom(move); 
              to = generateMoveTo(move); 
              fromX = getXFromLocation(from); 
              fromY = getYFromLocation(from);
              toX = getXFromLocation(to);
              toY = getYFromLocation(to); 
              printf("\n电脑所走的棋是：from (%d,%d) to (%d,%d)\n", fromX, fromY, toX, toY);
            }
          }
        }
      }
    }
  }
  return 0;
}